package book;

public class ClimbStairsSolution {
    
    // 优化前的版本，空间复杂度O(n)
    // 爬楼梯，给定整数n表示总共n级楼梯
    // 每次爬1或2级，求不同方案的总数
    public int climbStairs1(int n) {
        // 创建备忘录数组
        // dp[x]表示爬x级台阶的总数
        // 即数组中每个数值即为一个子问题的解
        int[] dp = new int[n + 1];
        // 初始化
        dp[0] = dp[1] = 1;
        // 逐步求解所有的子问题
        for (int i = 2; i <= n; i++) 
            // 递推公式：跳到当前台阶i的方案数等于
            // 跳到i-1与i-2级台阶的方案数之和
            dp[i] = dp[i - 1] + dp[i - 2];

        // 备忘录最后一个值即为原问题的解
        return dp[n];
    }

    // 优化后的版本，不再需要数组，空间复杂度为O(1)
    public int climbStairs(int n) {
        // 用两个变量滚动计算，d1表示dp[i]，d2表示dp[i-1]
        int d1 = 1, d2 = 1;

        // 依然逐步求解所有的子问题
        for (int i = 2; i <= n; i++) {
            // 临时变量防数据丢失
            int temp = d1;
            // 递推公式：跳到当前台阶i的方案数等于
            // 跳到i-1与i-2级台阶的方案数之和
            d1 = d1 + d2;
            // 传递上一步的d1到这一步的d2
            d2 = temp;
        }

        // d1保存的是最后一次计算的结果，即问题答案
        return d1;
    }

    public static void main(String[] args) {
        int n = 30;
        int ans = new ClimbStairsSolution().climbStairs(n);
        System.out.println("跳上30级台阶的方案总数为: " + ans);
    }
}
